//
// Created by bleedingfight on 2020/7/5.
//
#include "intersection.h"

<<<<<<< HEAD:cxx/algorithm/src/intersection.cc
std::vector<int> intersection(std::vector<int> &nums1, std::vector<int> &nums2) {
    std::set<int> num1_set = std::set<int>(nums1.begin(), nums1.end());
    std::set<int> num2_set = std::set<int>(nums2.begin(), nums2.end());
    std::vector<int> result;
    std::set_intersection(num1_set.begin(), num1_set.end(), num2_set.begin(), num2_set.end(),
                          std::insert_iterator<std::vector<int> >(result, result.begin()));
    return result;
}

std::map<int, int> num_frequency(std::vector<int> &nums1) {
    std::map<int, int> num_map;
    for (auto iter = nums1.begin(); iter != nums1.end(); iter++) {
        if (num_map.count(*iter))
            num_map[*iter] += 1;
        else
            num_map[*iter] = 1;
    }
    return num_map;
}

std::vector<int> intersect(std::vector<int> &nums1, std::vector<int> &nums2) {
    std::map<int, int> num1_map = num_frequency(nums1);
    std::map<int, int> num2_map = num_frequency(nums2);
    std::vector<int> result;
    std::map<int, int> min_map;
    std::map<int, int> max_map;
    if (num1_map.size() > num2_map.size()) {
        min_map = num2_map;
        max_map = num1_map;
    } else {
        min_map = num1_map;
        max_map = num2_map;
    }
    for (auto keyvalue:min_map) {
        int key = keyvalue.first;
        int value = keyvalue.second;
        if (max_map.count(key)) {
            int min_count = max_map[key] < value ? max_map[key] : value;
            for (int i = 0; i < min_count; i++) {
                result.push_back(key);
            }
        }
    }
    return result;
=======
std::vector<int> intersection(std::vector<int> &nums1,
                              std::vector<int> &nums2) {
  std::set<int> num1_set = std::set<int>(nums1.begin(), nums1.end());
  std::set<int> num2_set = std::set<int>(nums2.begin(), nums2.end());
  std::vector<int> result;
  std::set_intersection(
      num1_set.begin(), num1_set.end(), num2_set.begin(), num2_set.end(),
      std::insert_iterator<std::vector<int> >(result, result.begin()));
  return result;
}

std::map<int, int> num_frequency(std::vector<int> &nums1) {
  std::map<int, int> num_map;
  for (auto iter = nums1.begin(); iter != nums1.end(); iter++) {
    if (num_map.count(*iter))
      num_map[*iter] += 1;
    else
      num_map[*iter] = 1;
  }
  return num_map;
}

std::vector<int> intersect(std::vector<int> &nums1, std::vector<int> &nums2) {
  std::map<int, int> num1_map = num_frequency(nums1);
  std::map<int, int> num2_map = num_frequency(nums2);
  std::vector<int> result;
  std::map<int, int> min_map;
  std::map<int, int> max_map;
  if (num1_map.size() > num2_map.size()) {
    min_map = num2_map;
    max_map = num1_map;
  } else {
    min_map = num1_map;
    max_map = num2_map;
  }
  for (auto keyvalue : min_map) {
    int key = keyvalue.first;
    int value = keyvalue.second;
    if (max_map.count(key)) {
      int min_count = max_map[key] < value ? max_map[key] : value;
      for (int i = 0; i < min_count; i++) {
        result.push_back(key);
      }
    }
  }
  return result;
>>>>>>> dev:cxx/algorithm/common/src/intersection.cc
}